/*
 * @lc app=leetcode.cn id=522 lang=cpp
 *
 * [522] 最长特殊序列 II
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        // return a != b ? max(a.length(), b.length()) : -1;
        // 每个字符都是自己的子序列，特殊序列又只能是一个字符的子序列，也就是特殊字符只能是自己的子序列。
        // 说人话就是，特殊字符没爹。
        // 题目实际就是找数组中，最长的孤儿。

        // sort by length, from long to short

// comp必须是一个严格弱排序的性质的比较器。

// 严格弱排序：（a=50,b=60） a < b

// 对于a < b，满足 a < b
// 若交换两数： a=60，b=50,此时应该返回false， 60 < 50（不满足，返回false）

// 在sort函数比较的时候，它会严格弱排序，比较 a是否 >= b，然后两个对象会进行交换，重新比较一遍，相当于这次比较的是 b是否>= a

// a >= b ？ 满足： true
// b <= a ? 满足： true
// 这样就出现了一个冲突，不管是a >= b还是b >= a都会返回true的情况，我们都知道sort中只要comp返回true，两个元素就会交换一次，因此comp返回两次true，会对两个元素交换两次，相当于没有交换，因此就会出现无效的比较器的情况。
// 正确的交换方式： 当 == 的时候，他们不用交换就可以了，此时如果两个元素相等，则都返回false，因此两次false，在sort中就不用交换，因此达到了等于时不交换的目标。

        struct CompareLength {
            bool operator() (const string& left, const string& right) {
                // can't be >=
                return left.size() > right.size();
            }
        };
        sort(strs.begin(), strs.end(), CompareLength());
        
        // sort(strs.begin(), strs.end(), [](string& lhs, string& rhs) { return lhs.size() > rhs.size(); });

        int n = strs.size();
        for (int i=0;i<n;++i) {            
            bool isSon = false;
            // search its father from 0, shorter str impossible
            for (int j=0;j<n;++j) {
                // check self
                if (i == j) {continue;}
                if (strs[j].size() < strs[i].size()) {break;}

                if (leftIsSonOfRight(strs[i], strs[j])) {
                    isSon = true;
                    break;
                }
            }

            if (!isSon) {
                return strs[i].size();}
        }

        return -1;
    }
private:
    bool leftIsSonOfRight(const string& left, const string& right) {
        if (left.size() > right.size()) {return false;}
        else if (left.size() == right.size()) {return left == right;}
        else {
            // left is shorter, check it

            // int rightPointer = 0;
            // for (int i=0;i<left.size();++i) {
            //     while (left[i] != right[rightPointer]) {
            //         rightPointer += 1;
            //         if (rightPointer == right.size()) {return false;}
            //     }
            // }
            // return true;

            int leftPointer = 0, rightPointer = 0;
            while(leftPointer < left.length() and rightPointer < right.length()){
                if(left[leftPointer] == right[rightPointer]) {
                    leftPointer++;
                }
                rightPointer++;
            }
            return leftPointer == left.size();
        }
    }
};
// @lc code=end


// ["a","aa","aaa","aa"]

int main() {
    // vector<string> strs = {"a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"};
    vector<string> strs = {
        "a","a","a","a","a","a","a","a","a","a",
        "a","a","a","a","a","a","a"
    };
    Solution test;
    test.findLUSlength(strs);
}
